#pragma once

#include <vector>
#include <string>
#include <iostream>

static std::vector<int> pattern_table(const std::string& pat) {
    std::size_t word_len = pat.size();
    std::vector<int> tbl (word_len, 0);
    if (word_len < 2) {
        return std::move(tbl);
    }

    std::size_t pos = 2;
    std::size_t cnd = 0;

    while (pos < word_len) {
        if (pat[cnd] == pat[pos-1]) {
            ++cnd;
            tbl[pos] = cnd;
            ++pos;
        } else if (cnd > 0) {
            cnd = tbl[cnd];
        } else {
            tbl[pos] = 0;
            ++pos;
        }
    }

    return std::move(tbl);
}

static int kmp_search(const std::string& context, const std::string& pat) {
    auto pat_table = pattern_table(pat);
    std::size_t context_len = context.size();
    std::size_t pattern_len = pat.size();
	std::size_t j = 0;
    for (std::size_t i = 0; i < context_len; ) {
		std::cout << "compare : " << context[i] << " <==> " << pat[j] << "  index: " << i << " <==> "<< j << std::endl;
		if (context[i] != pat[j]) {
			if (j > 0) {
				std::cout << "set pattern index !" << j << " -> " << pat_table[j] << std::endl;
				j = pat_table[j];
			} 
		} else {
			++j;
		}

		++i;
		//if (j > pattern_len) {
		//	std::cout << "fatal error!" <<  j << std::endl;
		//	return -1;
		//}

		if (j == pattern_len) {
			return i - j;
		}
    }

    return -1;
}
